A storage system is a computer that provides access to information that is stored on one or more storage devices connected to the storage system, such as disk drives (“disks”), flash memories, or storage arrays. The storage system includes an operating system that may implement a file system to logically organize the information as a hierarchical structure of directories and files on a storage device (e.g., disks). Each file may be implemented as set of data structures, e.g., disk blocks, configured to store information, such as the actual data for the file.
A storage system may be further configured to operate according to a client/server model of information delivery to thereby allow many clients to access files stored on the storage system. In this model, the client may comprise an application executing on a computer that “connects” to the storage system over a computer network, such as a point-to-point link, shared local area network, wide area network or virtual private network implemented over a public network, such as the Internet.
In the operation of a storage array, it is fairly common that a disk, or other storage medium, such as flash memory, will fail. Data can be lost when one or more storage devices fail, making it impossible to recover data from the device. A typical scheme to avoid loss of data is parity protection wherein redundant encoding of the data allows for the loss of one or more disks without the loss of data.
A parity value may be computed by computing data across a number of similar disks holding different data and then storing the results in the array. Thus, if the disk storing parity values are lost, a parity value can be regenerated or reconstructed from the data on surviving disks. If one of the data disks is lost, the data can be reconstructed by computing the contents of the surviving disks using the parity values.
In one conventional implementation, disks are arranged into parity groups, each of which includes one or more data disks and at least one parity disk. The data structures representing the array are arranged into “stripes”, with each stripe containing one block from each disk. Within a stripe, a portion of blocks contain data (“data blocks”) and at least one block (not a data block) is a block which contains parity (“parity block”). The parity value stored on a parity block may be computed by, for example, the exclusive-OR (XOR) of all the data from all the data blocks.
If the parity blocks from each stripe are all stored on one disk, thereby providing a single disk that contains all (and only) parity information, the system is referred to as a Redundant Array of Inexpensive (or Independent) Disks level four implementation (RAID-4). This can be contrasted from a RAID-5 implementation which distributes the parity blocks across all disks in the array. In a dual parity scheme, e.g. RAID Double (or Diagonal) Parity (RAID-DP), a technique invented by NetApp, Inc. (formerly Network Appliance, Inc.) of Sunnyvale, Calif., data loss resulting from a two-disk failure can be reconstructed using two parity blocks. In RAID-DP, two dedicated disks serve as parity disks, wherein the first parity disk stores parity values from data computed across a single row stripe. The second parity disk stores parity values from data computed across staggered blocks (including a parity block from the first parity disk), otherwise referred to as a diagonal stripe.
In the physical operation of a disk, a disk is a self-contained rotating magnetic media storage device and data is accessed for input/output (I/O) operations when a stationary disk head positioned above the surface of a revolving disk writes data to or reads data from a physical location on disk. In the absence of disk access requests, i.e. I/O requests, a disk continues to revolve while awaiting its next request.
During reconstruction, resources of a storage system may be tied up reconstructing content from disk blocks (data values), as well as performing other activities such as data processing or servicing other I/O requests before providing data to a replacement disk. In the meantime, the replacement disk continues to revolve while awaiting a request to write a reconstructed data value to the replacement disk. Data may therefore not be supplied fast enough to the replacement disk to avoid wasted revolutions before receiving the request. This results in delays during reconstruction, thus affecting both performance and speed of a storage system.